public class LC0011 {
    /**
     * 双指针解法，令两个指针在开始时指向数组两端，每次容器的容量，并令指向元素较小的指针向对侧移动，直至指针重合。
     * 这种做法可以被看做是一种高效的剪枝。本质上仍然需要遍历所有可能的组合来找最大值。然而，让较大的指针向较小的指针移动必不可能产生更大的容量，
     * 因此可以舍去这些操作，每次舍去的操作为O(N)级别。通过这种高效的剪枝，算法的时间复杂度可以降到O(N)。
     * 进一步地，当两个指针指向的数字相等时，无论哪个指针向对向移动，都不可能产生更大的容量，因此实际上可以让两个指针同时向中心移动。
     * 时间复杂度：N，空间复杂度：1
     */
    public int maxArea(int[] height) {
        int length = height.length;
        int left = 0, right = length - 1;
        int maxVolume = Math.min(height[left], height[right]) * (right - left);
        do {
            if (height[left] < height[right]) left++;
            else if (height[left] > height[right]) right--;
            else { // 无论单方面移动哪个指针，都不可能产生更大的容量，因此同时移动两个指针
                left++;
                right--;
            }

            int volume = Math.min(height[left], height[right]) * (right - left);
            if (volume > maxVolume) maxVolume = volume;
        } while (left < right);

        return maxVolume;
    }
}
